home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / lib / tex / inputs / TreeClasses.tex < prev    next >
Text File  |  1991-05-20  |  3KB  |  102 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%% Complete binary trees                                                  %%%
  3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  4.  
  5. % The macro \b@nary{<number>} expands to the description of a complete
  6. % binary tree with <number> many internal nodes, where each level is filled with
  7. % the maximal number of internal nodes, and the last level of internal nodes
  8. % is filled from left to right.
  9.  
  10. \newcount\b@nno % number of nodes
  11. \newcount\b@nlv % number of complete levels
  12. \newcount\b@ndl % number of nodes on incomplete level
  13.  
  14. \def\ld(#1,#2,#3){% #1, #2, and #3 must be counter registers.
  15.                   % #1 is the input, #1 must be >= 1.
  16.                   % \ld makes the following assignments:
  17.                   % #2:=|_log_2(#1)_|, #3:=2^#2.
  18.                   % The contents of #1 is destroyed during the computation.
  19.      #2=0 #3=1
  20.        \loop\ifnum #1>\@ne\relax
  21.             \divide #1 by\tw@ % this is integer division
  22.             \advance #2 by\@ne
  23.             \multiply #3 by\tw@
  24.      \repeat}
  25.  
  26. \def\b@nary#1{% draws a complete binary tree with #1 internal nodes,
  27.            % a complete binary tree with N internal nodes has 
  28.            % lv:=|_log_2(N+1)_| many
  29.            % complete level of binary nodes and dl:=N-2^{lv}+1 many internal
  30.            % nodes on an incomplete level.
  31.      \b@nno=#1\relax\advance\b@nno by \@ne
  32.      \ld(\b@nno,\b@nlv,\b@ndl)%
  33.      \b@ndl=-\b@ndl\advance\b@ndl by #1\advance\b@ndl by\@ne
  34.      \b@n}
  35.  
  36. \def\b@n{%
  37.      \ifnum\b@nlv>\@ne
  38.            \advance\b@nlv by-\@ne
  39.            \b@n
  40.            \b@n
  41.            \advance\b@nlv by\@ne
  42.            \node{}
  43.       \else\ifnum\b@ndl>\@ne
  44.                  \advance\b@ndl by-\tw@
  45.                  \node{\le@f\external}\node{\le@f\external}\node{}%
  46.                  \node{\le@f\external}\node{\le@f\external}\node{}%
  47.                  \node{}%
  48.             \else\ifnum\b@ndl=\@ne
  49.                        \advance\b@ndl by-\@ne
  50.                        \node{\le@f\external}\node{\le@f\external}\node{}%
  51.                        \node{\le@f\external}%
  52.                        \node{}%
  53.                   \else\node{\le@f\external}\node{\le@f\external}\node{}%
  54.                     \fi
  55.               \fi
  56.         \fi}
  57.  
  58. \def\circleleaves{\def\le@f{\type{circle}}}
  59. \def\squareleaves{\def\le@f{\type{square}}}
  60.  
  61. \newcount\no@
  62. \def\no#1{\no@=#1\relax}
  63.  
  64. \def\binary#1{%
  65.      \no{1}\circleleaves
  66.      #1%
  67.      \b@nary{\no@}}
  68.  
  69. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  70. %%% Fibonacci trees                                                        %%%
  71. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  72.  
  73. % \f@b expands to the description of a Fibonacci tree
  74. % of height \f@bht.
  75.  
  76. \newcount\f@bht
  77.  
  78. \def\f@b{% draws a Fibonacci tree of depth #1
  79.      \ifnum\f@bht>1
  80.            \advance\f@bht by-\@ne\f@b\advance\f@bht by\@ne
  81.            \advance\f@bht by-\tw@\f@b\advance\f@bht by\tw@
  82.            \ifunn@des\node{\unary}
  83.                   \fi
  84.            \node{\lefttop}
  85.       \else\ifnum\f@bht=1
  86.                  \node{\external\le@f}
  87.                  \node{\external\le@f}
  88.                  \node{}
  89.             \else\node{\external\le@f}
  90.               \fi
  91.         \fi}
  92.  
  93. \newif\ifunn@des
  94.  
  95. \let\unarynodes\unn@destrue
  96. \def\hght#1{\f@bht=#1\relax}
  97.  
  98. \def\fibonacci#1{%
  99.      \hght{0}\unn@desfalse\circleleaves
  100.      #1%
  101.      \f@b}
  102.